In a conventional art, acquisition and process of a signal in wireless communication are achieved in four steps of sampling, compressing, transmitting and decompressing. Practically, in a case that the signal is compressible, whether the sampling and the compressing are merged into one step is considerable. In 2006, it has been proved by Candes that, a signal can be reconstructed accurately from a part of Fourier transform coefficients of the signal, which is a theoretical basis for the compressive sensing.
A process of the compressive sensing algorithm may be represents by y=Φs. It is assumed that y200=Φ200*800s800, where s is an original signal and is a column vector with N items, and s has a spare representation. That is to say, after an orthogonal transformation on Φ, Φs=x has K (<<N) non-zero items with unknown locations. y is a linear measurement and is a column vector with M items (M<<N and M>2K), and Φ is a measurement (projection) matrix with M rows and N columns. A condition for accurate reconstruction of the original signal s is as follows. Under the constraint condition y=Φs=ΦΨHx=Tx, x with the minimum number of non-zero elements is found, and then s=ΨHx is calculated, where T=ΦΨH is referred to as a sensing matrix.
The reconstructing algorithm based on the compressive sensing is to reconstruct the original signal based on the measurement and the measurement matrix. The process of the reconstruction algorithm is converted to the minimum l0 norm optimization problem described above, which is a NP-hard problem and needs to exhaust all of the infinite possible combination of non-zero x′ and thus it is impossible to solve. In industry, it is provided multiple methods for founding the suboptional solution, including the minimum l0 norm method, the matching pursuit method and the like. The implementation complexity of the minimum l0 norm method is generally O(N3), which is in direct proportion to N3. The implementation complexity of the matching pursuit method may be O(N), which is in direct proportion to N. If the information symbol in the OFDM (Orthogonal Frequency Division Multiplexing, orthogonal frequency division multiplexing, abbreviate to OFDM) baseband signal is reconstructed by using the conventional compressive sensing algorithm, the algorithm used by the receiver is very complex.